package main

import "fmt"

func main() {
	nums := []int{1, 2, 3, 4, 5}
	target := 4
	res := twoSum3(nums, target)
	fmt.Println(res)
}

//时间复杂度n2
func twoSum(nums []int, target int) []int {
	for k1, v1 := range nums {
		for k2, v2 := range nums {
			if v1+v2 == target {
				return []int{k1, k2}
			}
		}

	}

	return []int{}
}

//时间复杂度n
func twoSum2(nums []int, target int) []int {
	a := make(map[int]int)
	for k, v := range nums {
		a[v] = k
	}

	for k, v := range nums {
		rest := target - v
		if j, ok := a[rest]; ok {
			return []int{k, j}
		}
	}
	return []int{}
}

func twoSum3(nums []int, target int) []int {
	m := make(map[int]int)
	for k, v := range nums {
		m[v] = k
	}

	for k1, v1 := range nums {
		rest := target - v1
		if k2, ok := m[rest]; ok && k1 != k2 {
			return []int{k1, k2}
		}
	}

	return []int{}
}
